package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2023-01-03 13:35:50	 当前时间
 */
//给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原
//始二叉搜索树中的任意节点值都不同。 
//
// 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [4,2,7,1,3], val = 5
//输出：[4,2,7,1,3,5]
//解释：另一个满足题目要求可以通过的树是：
//
// 
//
// 示例 2： 
//
// 
//输入：root = [40,20,60,10,30,50,70], val = 25
//输出：[40,20,60,10,30,50,70,null,null,25]
// 
//
// 示例 3： 
//
// 
//输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
//输出：[4,2,7,1,3,5]
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数将在 [0, 104]的范围内。 
// -108 <= Node.val <= 108 
// 所有值 Node.val 是 独一无二 的。 
// -108 <= val <= 108 
// 保证 val 在原始BST中不存在。 
// 
// Related Topics 树 二叉搜索树 二叉树 
// 👍 417 👎 0

public class 二叉搜索树中的插入操作{
	public static void main(String[] args) {
		Solution solution = new 二叉搜索树中的插入操作().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	/** 复习  @author 刘世锦
	 *  @date  2023/2/13 21:22
	 */

	public TreeNode insertIntoBST(TreeNode root, int val) {
		if (root==null){
			return new TreeNode(val);
		}
		if (root.val>val){
			root.left =  insertIntoBST(root.left,val);
		}else{
			root.right =  insertIntoBST(root.right,val);
		}
		return root;
	}

	// 复习end

	/**
	 * 递归返回值：需要插入的节点。
	 *
	 */
	public TreeNode insertIntoBSTBFS(TreeNode root, int val) {
		if (root==null){
			return new TreeNode(val);
		}
		if (root.val>val){
			root.left = insertIntoBST(root.left,val);
		}else{
			root.right = insertIntoBST(root.right,val);
		}
		return root;
	}

	public TreeNode insertIntoBST2(TreeNode root, int val) {
		if (root==null){
			return new TreeNode(val);
		}
		dfs(root,val);
		return root;
//		if (root==null){
//			return new TreeNode(val);
//		}
//		if (root.val>val){
//			root.left = insertIntoBST(root.left,val);
//		}else{
//			root.right = insertIntoBST(root.right,val);
//		}
//		return root;
	}

	TreeNode pre = null;
	private void dfs(TreeNode root, int val) {
		if (root==null){
			TreeNode node = new TreeNode(val);
			if (pre!=null){
				if (pre.val>val){
					pre.left = node;
				}else{
					pre.right = node;
				}
			}

		}else{
			if (root.val>val){
				pre = root;
				dfs(root.left,val);
			}else{
				pre = root;
				dfs(root.right,val);
			}
		}

	}

	public TreeNode insertIntoBST1(TreeNode root, int val) {
		if(root==null) {
			return new TreeNode(val);
		}
		TreeNode cur = root;
		while(root!=null){
			if(root.val>val ){
				if( root.left!=null){
					root = root.left;
				}else{
					root.left = new TreeNode(val);
					break;
				}
			}else  if(root.val<val ){
				if( root.right!=null){
					root = root.right;
				}else{
					root.right = new TreeNode(val);
					break;
				}
			}
		}
		return cur;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
